//
//  Sort.m
//  Sort
//
//  Created by sr Liu on 2020/4/11.
//  Copyright © 2020 sr Liu. All rights reserved.
//

#import "Sort.h"

@implementation Sort

/*
 不可能数据结构定义和算法完全记得跟书上一样, 尤其那个i=1 之类的下标
 就按核心思想，用最简单的定义，把排序过程写出来
 */


- (void)testSort {
//    int a[] = {2,4,1,3,8,5,9,6,7};
    int a[] = {9,8,7,6,5,4,3,2,1};
    for (int i = 0; i < 9; i++) {
        printf("%d",a[i]);
    }
    printf("\n");
    //开始排序
    shellSort(a, 9);
    for (int i = 0; i < 9; i++) {
        printf("%d",a[i]);
    }
    printf("\n");
}

- (void)testShell {
    int a[] = {49, 38, 65, 97, 76, 13, 27, 48, 55, 4};
    for (int i = 0; i < 10; i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
    shellSort(a, 10);
}

//归并
- (void)testMerge {
    //写10个数 第一个0
    int a[] = {0, 50, 10, 90, 30, 70, 40, 80, 60, 20};
    for (int i = 0; i < 10; i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
    mergeSort(a);
    for (int i = 0; i < 10; i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
}

- (void)testMergeSeq {
    //写10个数 第一个0
    int a[] = {0, 10, 30, 50, 20, 40, 60, 80, 100};
    for (int i = 0; i < 9; i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
    
    int b[10] = {0};
    merge(a, b, 1, 3, 8);
    
    
    for (int i = 0; i < 9; i++) {
        printf("%d ",b[i]);
    }
    printf("\n");
}

- (void)testHeapSort {
    //写10个数 第一个0
    int a[] = {0, 50, 70, 90, 60, 10, 40, 80, 30, 20};
    for (int i = 0; i < 10; i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
    HeapSort(a, 9);
    for (int i = 0; i < 10; i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
}

#pragma mark - 冒泡排序

/**
 从下往上冒泡,小的在上面前面
 O(n^2) 稳定的
 最外层理解为趟数，不如理解为先确定下标小的位置 outer,
 内层从底部（下标大的）网上依次对比
 */
void bubbleSort(int a[], int n) {
    //outer已经冒完泡的,或者趟数

    bool SWAP = true;
    for (int outer = 0; outer < n - 1 && SWAP; outer++) {
        SWAP = false;
        for (int index = n - 1; index > outer; index--) {
            if (a[index] < a[index-1]) {
                int temp = a[index];
                a[index] = a[index-1];
                a[index-1] = temp;
                SWAP = true;
            }
        }
    }
}
#pragma mark - 简单选择排序
/**
 简单选择排序
 O(n^2) 不稳定
 从小到大每一趟 找到一个最小的下标
 */
void selectSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int index = i;
        for (int j = i + 1; j <= n - 1; j++) {
            if (a[j] < a[index]) {
                index = j;
            }
        }
        if (index != i) {
             swap(a, i, index);
        }
    }
}

#pragma mark - 直接插入排序
/**
 直接插入排序
 */
void insertSort(int a[], int n) {
    if (n < 2) {
        return;
    }
    for (int i = 1; i <= n - 1; i++) {
        int temp = a[i];//i待排序的下标
        int j = i - 1;
        while (j >= 0 && temp < a[j]) {
            a[j+1] = a[j];//往后排
            j--;
        }
        //注意循环里多减了一个
        a[j+1] = temp;
    }
    
}

#pragma mark - 希尔排序
/**
 希尔排序
 */

void shellSort(int a[], int n) {
    //也可以选择 for(d=n/2;d>=1;d=d/2)  来作为步长
    int dt[3] = {5, 3, 1};
    for (int i = 0; i < 3; i++) {
        shellSortInsert(a, dt[i], n);
        for (int i = 0; i < 10; i++) {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
}

void shellSortInsert (int a[], int dt, int n) {
    //进行直接插入排序
    if (n < dt + 1) {
        return;
    }
    //从dt开始往前找。。。多看几遍过程
    for (int i = dt; i <= n - 1; i++) {
        int temp = a[i];
        int j = i - dt;
        while (j >= 0 && temp < a[j]) {
            a[j+dt] = a[j];//往后排
            j = j - dt;
        }
        a[j+dt] = temp;
    }
}

#pragma mark - 堆排序
/**
 堆排序：
 注意：数组要排列成完全二叉树。
 然后建堆，取值再次建堆。
 从n/2处往上循环
 每一次建堆，都是节点往下找。
 */
//数组第一个0标 不存数据，方便和树的节点顺序对应,便于理解 a[length] 是最后一个数据
void HeapSort(int a[], int length) {
    
    for (int nodeIndex = length / 2; nodeIndex > 0; nodeIndex--) {
        headAdjust(a, nodeIndex, length);
    }
    //把后面的数据和顶部交换，逆序的过程，所以大顶堆对应的是从小到大的排序。
    for (int nodeIndex = length; nodeIndex > 1; nodeIndex--) {
        swap(a, nodeIndex, 1);
        headAdjust(a, 1, nodeIndex - 1);
    }
}

//数组a中 （waitIndex,end] 满足堆了，调整waitIndex关键字,成为一个大顶堆
void headAdjust(int a[], int waitIndex, int end) {
    int tempValue = a[waitIndex];
    for (int index = 2 * waitIndex; index <= end; index *= 2) {
        if (index < end && a[index] < a[index + 1]) {//是否右孩子更大
            index++;
        }
        if (tempValue >= a[index]) {//当前值已经比孩子大就停止
            break;
        }
        a[waitIndex] = a[index];//孩子的值覆盖当前值
        waitIndex = index;//记下索引
    }
    a[waitIndex] = tempValue;//放到最终位置上
}

#pragma mark - 归并排序
//参考大话中图解,翻转的完全二叉树
#define N 9

//数组第一个下标0位 不存数据. 下面相关方法都是如此。所以注意边界值就行了。
/**归并排序*/
void mergeSort (int a[]) {
    mSort(a, a, 1, N);
}

//将旧数组的数据,归并排序到新数组中,下标为start 到 end
void mSort (int old[], int new[], int start, int end) {

    if (start == end) {
        new[start] = old[start];
    } else {
        int midIndex = (start + end) / 2;;//找出分界点
        int newTempArr[10] = {0};
        mSort(old, newTempArr, start, midIndex);
        mSort(old, newTempArr, midIndex + 1, end);
        merge(newTempArr, new, start, midIndex, end);
    }
    
}

/**
 将a数组中start到mid数据 和 a数组中mid到end的数据，
 归并到b数组中，起始位置是start到end。索引前开后闭
 */

void merge(int a[], int b[], int start, int mid, int end) {
    
    //有序表的合并
    int aFirst_Index;
    int aSecond_Index;
    int bIndex;
    for (aFirst_Index = start, aSecond_Index = mid + 1, bIndex = start ; aFirst_Index <= mid && aSecond_Index <= end; bIndex++) {
        if (a[aFirst_Index] < a[aSecond_Index]) {
            b[bIndex] = a[aFirst_Index];
            aFirst_Index++;
        } else {
            b[bIndex] = a[aSecond_Index];
            aSecond_Index++;
        }
    }
    
    if (aFirst_Index <= mid) {//说明a的前半段还有剩余
        for (int r = aFirst_Index; r <= mid; r++) {
            b[bIndex] = a[r];
            bIndex++;
        }
    }
    
    if (aSecond_Index <= end) {//说明a的后半段还有剩余
        for (int r = aSecond_Index; r <= end; r++) {
            b[bIndex] = a[r];
            bIndex++;
        }
    }
    
}

#pragma mark - tool method
void swap(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

//折半插入排序，基数排序。还没看。不看了

@end
